1. Field of the Invention
This invention relates to a system for processing arithmetic information. In a primary application the invention relates to the parallel processing of arithmetic operations such as addition, subtraction, multiplication, integer polynomial transforms, any number of such operations, or any combination thereof. In a further application this invention relates to organizing such a processor into a partitioned and highly structured form to facilitate design, construction, and modification of such processors.
2. Description of the Prior Art
Residue arithmetic, also referred to as modular arithmetic, number theoretic arithmetic, or arithmetic over a Galois field has been known for some time. In the 19th century K. F. Gauss introduced the concept of modular arithmetic. He discovered that any calculation involving only additions, subtractions, multiplications, integer polynomial transforms, or any combination of these operations can be performed in a modular manner. In other words if all the operands, intermediate and final results are expressed as remainders of a given divisor then the equality of the overall expression would be preserved. It was also shown that if these calculations were duplicated for particular divisors then the modular results could be woven to resynthesize the traditional answer. One of the weaving techniques relies on Euclid's base conversion algorithm while the other technique relies on the Chinese Remainder theorem credited to Sun Tsu in 100 AD.
Residue arithmetic is unique in that no borrows or carries are used. This simplifies the circuitry needed since the carries or borrows need not be communicated, waited for, or stored. The arithmetic is simple and can be implemented with table lookups. A good review of the field is given in the book Residue Arithmetic and Its Application to Computer Technology by N. S. Szabo and R. I. Tanaka (N.Y., McGraw-Hill, 1967).
There are several problems associated with using the residue number system which has impeded its acceptance. One reason is that generalized division cannot be accomplished in an easy manner. Another is that encoding into residue and decoding out residues contributes a significant computational overhead. And finally relative magnitude or sign detection cannot be accomplished without first decoding from residues.
A processor which utilizes the advantages of residue arithmetic is described in a U.S. Pat. No. 4,107,783 issued to Alan Huang on Aug. 15, 1978. The system described amortizes the computational overhead of the required encoding and decoding by processing a plurality of operands and operations. If only two numbers were to be added then the benefits of a residue approach would be questionable, however if many numbers were to be added then the avoided carries would compensate for the required encoding and decoding overhead.
The processor described also utilizes another aspect of the residue system. The computational interactions of the processor are very simple and can be expressed as mappings or table look-ups. This facilitates the partitioning of the processor into basic building blocks which can be implemented by a wide range of technologies. In turn the different properties of these technologies enable a processor so constructed to process several unique properties.
The processor described in the patent is essentially a cascaded structure. Such an architecture is characterized by an intermediate result interacting in sequence with other operands. It is most suited to algorithms which can be represented by extended expression evaluation trees.
The present invention is also designed to handle a plurality of operands and operations, however they are handled in a parallel rather than a cascaded manner. Such a structure can process a plurality of intermediate results each interacting with different operands or among themselves. This parallel architecture is more general in that it can be applied to algorithms represented by any type of expression evaluation tree.
As mentioned previously the compatibility of residue results with conventional processors has been a major difficulty. This invention includes a means of converting from residues to conventional binary. Another problem which is addressed is the correct handling of sign information in the encoding, processing, and decoding processes.
Large conventional processors must contend with increased fabrication and internal communication problems associated with any increase in complexity. Recent efforts to overcome this problem have centered around using VLSI technology. Much work has been done in trying to partition processors into cellular arrays. Many approaches have been suggested, however an orderly structure seems to come at the expense of increased internal communications. By using the residue number system the internal communications related to arithmetic can be greatly be reduced. Thus this invention is also directed to a highly structured architecture which is easy to design, construct, and modify.